package algorithm_demo.demo_advanced;

import java.util.ArrayList;

/**
 * 给你两棵树，一棵树T1（二叉树）head1为头节点，另外一棵T2（二叉树）head2为头节点，
 * head2所延伸出的值的结构，对应的关系是不是T1某一棵子树的结构关系
 * @author Api
 * @date 2023/3/30 22:45
 */
public class Code12_TreeEquals {
    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int value){
            this.value = value;
        }
    }

    //big做头节点的树，其中是否有某棵子树的结构，是和small为头的树，完全一样的
    public static boolean containsTree1(Node big, Node small){
        if (small == null){
            return true;
        }
        //small != null
        if (big == null){
            return false;
        }
        //big!=null small !=null
        if (isSameValueStructure(big, small)){
            return true;
        }
        return containsTree1(big.left, small) || containsTree1(big.right, small);
    }

    //head1为头的树，是否在结构对应上，完全和head2一样
    //就是判断head1整棵树和head2整棵树结构上是否一样
    public static boolean isSameValueStructure(Node head1, Node head2){
        if (head1 == null && head2 != null){
            return false;
        }
        if (head1 != null && head2 == null){
            return false;
        }
        if (head1 == null && head2 == null){
            return true;
        }
        if (head1.value != head2.value){
            return false;
        }
        //head1.value == head2.value
        return isSameValueStructure(head1.left, head2.left)
            && isSameValueStructure(head1.right, head2.right);
    }

    public static boolean containsTree2(Node big, Node small){
        if (small == null){
            return true;
        }
        if (big == null){
            return false;
        }
        ArrayList<String> b = preSerial(big);
        ArrayList<String> s = preSerial(small);
        String[] str = new String[b.size()];
        for(int i = 0; i< str.length;i++){
            str[i] = b.get(i);
        }
        String[] match = new String[s.size()];
        for(int i = 0; i<match.length;i++){
            match[i] = s.get(i);
        }
        return getIndexOf(str, match) != -1;
    }

    public static int getIndexOf(String[] str1, String[] str2){
        if (str1 == null || str2 == null || str1.length<1 || str1.length< str2.length){
            return -1;
        }
        int x = 0;
        int y = 0;
        int[] next = getNextArray(str2);
        while(x<str1.length && y<str2.length){
            if (isEqual(str1[x], str2[y])){
                x++;
                y++;
            }else if (next[y] == -1){
                x++;
            }else{
                y = next[y];
            }
        }
        return y == str2.length? x-y:-1;
    }

    public static int[] getNextArray(String[] ms){
        if (ms.length == 1){
            return new int[]{-1};
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while(i<next.length){
            if (isEqual(ms[i-1], ms[cn])){
                next[i++] = ++cn;
            }else if (cn > 0){
                cn = next[cn];
            }else{
                next[i++] = 0;
            }
        }
        return next;
    }

    public static boolean isEqual(String a, String b){
        if (a == null && b == null){
            return true;
        }else{
            if (a == null || b == null){
                return false;
            }else{
                return a.equals(b);
            }
        }
    }

    public static ArrayList<String> preSerial(Node head){
        ArrayList<String> ans = new ArrayList<>();
        pres(head, ans);
        return ans;
    }
    public static void pres(Node head, ArrayList<String> ans){
        if (head == null){
            ans.add(null);
        }else{
            ans.add(String.valueOf(head.value));
            pres(head.left, ans);
            pres(head.right, ans);
        }
    }
}
